原题地址:螺旋矩阵 II
给定一个正整数 $n$,生成一个包含 $1$ 到 $n^2$ 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
逐层生成
按照螺旋矩阵的规则,从内向外逐层生成即可:
/**
* @param {number} n
* @return {number[][]}
*/
const generateMatrix1 = function(n) {
// 构建一个n*n的二维数组
let array = new Array(n);
for (let i = 0; i < n; i ++) {
array[i] = new Array(n);
}
let number = 1;
// 分层处理
for(let i = 0; i < n/2; i ++) {
// 上
for (let j = i; j < n - i - 1; j ++) {
array[i][j] = number ++;
}
// 右
for (let j = i; j < n - i - 1; j ++) {
array[j][n - i - 1] = number ++;
}
// 下
for (let j = n - i - 1; j > i; j --) {
array[n - i - 1][j] = number ++;
}
// 左
for (let j = n - i - 1; j > i; j --) {
array[j][i] = number ++;
}
}
// n为奇数时补上最中间的数
if (number === n * n) {
array[(n-1)/2][(n-1)/2] = number;
}
return array;
};
测试:
let start = new Date();
const test = generateMatrix1;
/**
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ],
]
*/
console.log(test(3));
/**
[
[ 1, 2, 3, 4 ],
[ 12, 13, 14, 5 ],
[ 11, 16, 15, 6 ],
[ 10, 9, 8, 7 ]
]
*/
console.log(test(4));
console.log(new Date().getTime() - start.getTime()); // 9
时间复杂度: 每个数字需要一次操作来填充,时间复杂度为$O(N^2)$
空间复杂度: 一个二个数组来存储结果,空间复杂度为$O(N^2)$
本文由 李海平 创作,采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Aug 17,2019